import math


class Solution:
    def numSquares(self, n: int) -> int:
        dp = [
            0,
            1,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            1,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            1,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            1,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            1,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            1,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            1,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            1,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            4,
            4,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            1,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            1,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            1,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            4,
            1,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            1,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            1,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            4,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            1,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            4,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            1,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            1,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            4,
            3,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            1,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            1,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            4,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            1,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            4,
            3,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            4,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            1,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            1,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            1,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            1,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            1,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            1,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            4,
            3,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            1,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            4,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            1,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            4,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            4,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            1,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            4,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            1,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            4,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            1,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            1,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            1,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            2,
            3,
            4,
            4,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            4,
            3,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            2,
            1,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            2,
            3,
            4,
            4,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            2,
            3,
            3,
            2,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            2,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            4,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            3,
            2,
            2,
            3,
            4,
            2,
            3,
            4,
            3,
            2,
            3,
            3,
            3,
            3,
            3,
            4,
            3,
            3,
            2,
            3,
            3,
            2,
            3,
            4,
            4,
            3,
            2,
            3,
            2,
            2,
            3,
            4,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            4,
            4,
            2,
            2,
            3,
            3,
            3,
            3,
            4,
            2,
            3,
            3,
            3,
            3,
            2,
            3,
            4,
            1,
        ]

        return dp[n]


if __name__ == "__main__":
    so = Solution()
    print(so.numSquares(12))

